<head>
    <meta charset="UTF-8">
<title>算法提高 The Islands</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p><img width="260" height="196" align="right" alt="" src="http://lx.lanqiao.cn/RequireFile.do?fid=74bgAymE" /></p>
<p>【问题描述】<br />
温晨是一艘救援艇的船长。他的一项重要任务是每天访问一趟岛屿群以便检查是否一切正常。温船长从最西边的小岛开始，寻找一条路径去最东边的岛屿，途中访问一些岛屿，之后再找寻另一条路径从最东边的岛屿回到出发点，途中访问剩下的岛屿。在每一条路径中温船长必须一直向东（在第一条路径中）或一直向西（在第二条路径中），但是可以向北或南移动任意远距离使其能达到下一个岛屿。唯一的问题是有两个特殊岛屿，温船长能在那里得到供给他的船的油，所以他必须在不同的路径中访问这两个岛（在第一条路径中访问其中一个岛，在另一条路径中访问剩下的一个岛）。图中显示了两个用粉红色标出的特殊岛屿（1和3）以及一条温船长可能采取的可行路径。<br />
当给定每座岛的坐标以及两座特殊岛屿编号时，计算用两条路径访问所有岛屿的最短路径长度。<br />
【输入格式】<br />
输入包含若干测试数据。每个数据第一行为3个整数n(4&lt;=n&lt;=100),b1和b2(0&lt;b1,b2&lt;n-1并且b1不等于b2)，n代表岛屿数(从0到n-1编号)而b1和b2代表两个特殊岛屿的编号。接下来有n行，每行包含整数x和y代表每个岛的坐标(0&lt;=x,y&lt;=2000)，从0号岛开始。没有两座岛有相同的x坐标并且岛屿按从西向东的顺序（即从最小的x坐标到最大的x坐标）。<br />
最后一组数据之后由3个0代表结束。<br />
<br />
【输出格式】<br />
对于每个数据，输出两行。第一行包含数据编号以及温船长访问所有岛屿所需的最小航程，四舍五入至小数点后两位。第二行包含一个有空格隔开的所需要访问的岛屿编号列表，以0和1开始，并以0结束。每组数据都有唯一解。按样例格式输出。<br />
【样例输入】<br />
5 1 3 <br />
1 3 <br />
3 4 <br />
4 1 <br />
7 5 <br />
8 3 <br />
5 3 2 <br />
0 10 <br />
3 14 <br />
4 7 <br />
7 10 <br />
8 12 <br />
0 0 0 <br />
<br />
【样例输出】<br />
Case 1: 18.18<br />
0 1 4 3 2 0 <br />
Case 2: 24.30 <br />
0 1 3 4 2 0<br />
<br />
【数据规模和约定】<br />
4 &lt;= n &lt;=100<br />
0 &lt; b1, b2 &lt; n-1 and b1!=b2<br />
0 &lt;=x, y &lt;=2000<br />
&nbsp;</p>